#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e3+10;

#define in read()

int n,m,h[MAXN],cnt,dis[MAXN],v[MAXN];
struct edge{int v,w,nxt;}e[MAXN<<1];
bool vis[MAXN];

void link(int x,int y,int w){e[++cnt]=(edge){y,w,h[x]};h[x]=cnt;}

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') sgn=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

void spfa(){
	queue<int> q;
	q.push(0);vis[0] = 1; memset(dis,0x3f,sizeof(dis));dis[0] = 0;
	while(q.size()){
		int x = q.front();q.pop();
		vis[x] = 0;v[x]++;
		if(v[x] > n) {
			printf("NO");
			exit(0);
		}
		for(int i = h[x];i;i = e[i].nxt){
			int y = e[i].v;
			if(dis[y] > dis[x] + e[i].w){
				dis[y] = dis[x] + e[i].w;
				if(!vis[y]) vis[y] = 1,q.push(y);
			}
		}
	}
}

int main (){
	n=in,m=in;
	for(int i = 1;i <= m;i++){
		int x = in,y = in,w = in;
		link(y,x,w);
	}
	for(int i = 1;i <= n;i++) link(0,i,0);
	spfa();
	for(int i = 1;i <= n;i++) printf("%d ",dis[i]);
}
